# 该文件用来调试 Leetcode 题目中的代码

# from collections import defaultdict
#
# s = "abcabcbb"
# ans = 0
# pre = 0
# d = defaultdict(int)
# for i in range(len(s)):
#     d[s[i]] += 1
#     while d[s[i]] > 1:
#         d[s[pre]] -= 1
#         pre += 1
#     ans = max(ans, i - pre + 1)
# from collections import defaultdict, Counter
#
# s = "cbaebabacd"
# p = "abc"
# ans = []
# left = 0
# conut_p = Counter(p)
# count_s = Counter()
# for i, v in enumerate(s):
#     count_s[v] += 1
#     length = i - left + 1
#     if length < len(p): continue
#     if conut_p == count_s:
#         ans.append(left)
#     count_s[s[left]] -= 1
#     left += 1
# print(ans)

# nums = [1]
# k = 0
# all_sum = 0
# ans = 0
# pre = 0
# for i in nums:
#     all_sum += i
#     if all_sum == k:
#         ans += 1
#     while all_sum > k:
#         all_sum -= nums[pre]
#         pre += 1
# print(ans)

# a = [10,2,34,3]
# print(a[1:3])
# print(max(a))

# nums = [1,3,-1,-3,5,3,6,7]
# k = 3
# ans = []
# pre = 0
# for i in range(len(nums) - k):
#     ans.append(max(nums[pre:pre + k]))
#     pre += 1
# print(ans)

# 汉诺塔问题
# def move(height,f,m,e):
#     if height >= 1:
#         move(height-1,f,e,m)
#         print(f"{height}move disk from {f} to {e}")
#         move(height-1,m,f,e)
#
# move(10,"A","B","C")
#
# s = "abc"
# print(s[0:len(s)+1])

# dp = [0, 0]
# cost = [1,100,1,1,1,100,1,1,100,1]
# for i in range(2, len(cost) + 1):
#     dp.append(min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]))
#     print(dp)


# m = 3
# n = 4
# dp = [[0] * n for _ in range(m)]
# print(dp)


# m = 3
# n = 7
# dp = [[0] * (n) for _ in range(m)]
# for i in range(n):
#     dp[0][i] = 1
# for i in range(m):
#     dp[i - 1][0] = 1
# for j in range(1, m):
#     for i in range(1, n):
#         dp[j][i] = dp[j - 1][i] + dp[j][i - 1]
# print(dp)

# obs = [[0,0,0],[0,1,0],[0,0,0]]
# obstacleGrid[i][0] = 1
# for i in range(len(obs)):
#     if obs[0][0] == 1 or obs[-1][-1] == 1:
#         break
#     fl = 1
#     for i in range(len(obs)):
#         if obs[i][0] != 1 and fl == 1:
#             obs[i][0] = 1
#         else:
#             fl = 0
#             obs[i][0] = 0
#     fl = 1
#     for i in range(1,len(obs[0])):
#         if obs[0][i] != 1 and fl == 1:
#             obs[0][i] = 1
#         else:
#             obs[0][i] = 0
#             fl = 0
#     print(obs)
#     print("-----------------")
#     for i in range(1, len(obs)):
#         for j in range(1, len(obs[0])):
#             if obs[i][j] == 1:
#                 obs[i][j] = 0
#                 continue
#             else:
#                 obs[i][j] = obs[i - 1][j] + obs[i][j - 1]
#     print(obs)


# n = 10
# path = []
# ans = []
# def backtracking(sum):
#     if sum == n:
#         ans.append(path.copy())
#         return
#     for i in range(1,n+1):
#         if sum + i > n:
#             break
#         path.append(i)
#         sum += i
#         backtracking(sum)
#         sum -= path.pop()
#     return
# backtracking(0)
# print(len(ans))
# print(ans)

# cache= [0] *10
# cache[0]=1
# print(cache)

# a = [1]
#
# for i in range(2,len(a)):
#     print(a[i])

# n = 10
# dp = [0] * (n + 1)
# dp[2] = 1
# print(dp)
# print(len(dp))
# for i in range(3, n+1):
#     for j in range(1, i):
#         dp[i] = max(dp[i - j] * j,dp[i],j*(i-j))
#         print("i = " , i  ,"J = ",j,end=" ")
#         print(dp)


# n = 4
# dp = [0] *(n+1)
# dp[0] = 1
# dp[1] = 1
# dp[2] = 2
#
# for i in range(3,n+1):
#     for j in range(1,i+1):
#         dp[i] += dp[j-1]*dp[i-j]
#         print("i = ", i ,"J = ",j,end=" ")
#         print(dp)

from collections import defaultdict, Counter

from sqlalchemy.util import counter

# d = {}
# n = 8
# ans = []
# end = []
# path = []
#
# for i in range(n+1):
#     d[i] = 0
# def backtracking(n):
#     if n == 0:
#         if d not in ans:
#             ans.append(d.copy())
#             end.append(path.copy())
#         return
#     for i in range(1, n + 1):
#         path.append(i)
#         d[i] += 1
#         backtracking(n - i)
#         d[i] -= 1
#         path.pop()
#     return
#
#
# backtracking(n)
# for i in end:
#     tem = 1
#     for j in i:
#         tem *= j
#     print("%2d" %tem, end="  ")
#     print(i)


# s = ['a','b','c']
# s1 = ['a','b','c']
# print(s == s1)


# s = "ab#c"
# t = "ad#c"

# s = "ab##"
# def ans(s):
#     tem = []
#     pre = 0
#     for i in range(1, len(s)):
#         if s[i] == '#':
#             pre = i + 1
#             i += 1
#         else:
#             tem.append(s[pre])
#     return tem


# print(ans(s) == ans(t))
# print(ans(s))

# s = []
# print(s != [])

# num = 5
# left = 1
# right = num
# while left <= right:
#     middle = (left + right) / 2
#     if middle * middle == num and middle == int(middle):
#         print("middle is", middle)
#         break
#     elif middle * middle == num:
#         break
#     elif middle * middle > num:
#         right = middle - 1
#     else:
#         left = middle + 1
# print("not found")

# d = defaultdict(int)
# for i in range(10):
#     d[i] += 1
# print(d)

# d = defaultdict(int)
# d1 = defaultdict(int)
# for i in range(10):
#     d[i] += 1
#     d1[i] += 1
# print(d == d1)

# s = "hello world"
# d = Counter(s)
# d1 = defaultdict(int)
# print(d)
# print(d.keys())

# n = 4
#
# a = [[0] * n for _ in range(n)]
# tem = 1
# for i in range(n):
#     # i 是遍历的圈数
#     for j in range(i,n - i - 1):
#         a[i][j] = tem
#         a[j][n-1-i] = tem + (n - 1 - 2*i)
#         a[n-1-i][n-1-j] = tem + 2 *(n - 1 -2*i)
#         a[n-1-j][i] = tem + 3 *(n - 1 -2*i)
#         tem += 1
#     tem += 3 * (n - 1 - 2 * i)
# if n % 2 == 1:
#     a[n//2][n//2] = n * n
#
# for p in a:
#     print(p)


# d = {}
# for i in range(10):
#     d[i] += 1
# print(d)

# class node:
#     def __init__(self, value, next=None):
#         self.value = value
#         self.next = next
# a = node('a')
# b = node('b')
# c = node('c')
#
# a.next = b
# b.next = c
#
# while a:
#     print(a.value)
#     a = a.next

# class Node:
#     def __init__(self, val, next):
#         self.val = val
#         self.next = next
#
#
# class MyLinkedList:
#
#     def __init__(self):
#         self.head = Node(0, None)
#
#     def get(self, index: int) -> int:
#         tem = self.head.next
#         while tem:
#             index -= 1
#             if index == -1:
#                 return tem.val
#             tem = tem.next
#         return -1
#
#     def addAtHead(self, val: int) -> None:
#         new = Node(val, self.head.next)
#         self.head.next = new
#
#     def addAtTail(self, val: int) -> None:
#         tem = self.head.next
#         while tem.next:
#             tem = tem.next
#         new = Node(val, None)
#         tem.next = new

    # def addAtIndex(self, index: int, val: int) -> None:
    #     tem = self.head.next
    #     while tem:
    #         if index <= 0:
    #
    # def deleteAtIndex(self, index: int) -> None:

# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

# obj = MyLinkedList()
# obj.addAtHead(1)
# obj.addAtTail(2)
# obj.addAtTail(3)
# obj.addAtTail(4)
# obj.addAtHead(5)
# print(obj.get(0))

# class Node:
#     def __init__(self, val, next):
#         self.val = val
#         self.next = next
#
#
# class MyLinkedList:
#
#     def __init__(self):
#         self.head = Node(0, None)
#
#     def get(self, index: int) -> int:
#         tem = self.head.next
#         while tem:
#             index -= 1
#             if index == -1:
#                 return tem.val
#             tem = tem.next
#         return -1
#
#     def addAtHead(self, val: int) -> None:
#         new = Node(val, self.head.next)
#         self.head.next = new
#
#     def addAtTail(self, val: int) -> None:
#         tem = self.head.next
#         while tem.next:
#             tem = tem.next
#         new = Node(val, None)
#         tem.next = new
#
#     def addAtIndex(self, index: int, val: int) -> None:
#         tem = self.head.next
#         while tem:
#             index -= 1
#             if index == -1 and tem.next:
#                 new = Node(val, tem.next)
#                 tem.next = new
#                 return
#             if index == -1 and tem.next is None:
#                 new = Node(val, None)
#                 tem.next = new
#             tem = tem.next
#
#     def deleteAtIndex(self, index: int) -> None:
#         tem = self.head.next
#         while tem:
#             index -= 1
#             if index == -1 and tem.next:
#                 tem.next = tem.next.next
#                 return
#             tem = tem.next
#
# obj = MyLinkedList()
# obj.addAtHead(1)
# obj.addAtTail(3)
# obj.addAtIndex(1, 2)
# obj.get(1)
# obj.deleteAtIndex(0)
# obj.get(0)

# class Node:
#     def __init__(self,value,next):
#         self.value = value
#         self.next = next
#
#
# a = Node('a',None)
# a1 = Node('a',None)
# b = Node('b',a)
# c = Node('c',a1)
#
# print(b.next == c.next)


# a = [1,2,3,3,1,5]
# print(Counter(a))
# print(Counter(a).keys())


# def num(a):
#     tem = str(a)
#     d = Counter(tem)
#     sum = 0
#     for i in d.keys():
#         sum += pow(int(i),2) *d[i]
#     print(sum)
#     if sum == 1:
#         return
#     else:
#         num(sum)
#
# num(44)

# nums = [2,7,11,15]
# target = 9
# d = Counter(nums)
# for i in nums:
#     if target - i in d.keys():
#         print(i, target - i)

# for i,val in enumerate(nums):
#     print(i,val)

#
# a = [[0]*5 for _ in range(5)]
# print(a)


# def reverseStr(s: str, k: int) -> str:
#     s = list(s)
#     for i in range(0, len(s), k * 2):
#         s[i: i + k] = s[i: i + k][::-1]  # 右端点自动和 n 取最小值
#     return ''.join(s)
#
#
# s = "abcdefgcc"
# print(len(s))
# print(len(s[0:10]))
# k = 2
# a = reverseStr(s, k)
# print(a)
#
#
# a = "ad"

# s = "the sky is blue"
# s = s.split(" ")
# ans = []
# for i in range(len(s)-1,-1,-1):
#     ans.append(s[i])
#
# print(" ".join(ans))

# s = "abcdefg"
# print(s.index("m"))

# nums = [2,6,7,3,1,7]
# m = 3
# k = 4
# d = defaultdict(int)
# ans = tem = pre = 0
# for i in range(k - 1):
#     tem += nums[i]
#     d[nums[i]] += 1
# for i in range(k - 1, len(nums)):
#     tem += nums[i]
#     d[nums[i]] += 1
#     if len(d.keys()) >= m:
#         ans = max(tem, ans)
#     d[nums[pre]] -= 1
#     if d[nums[pre]] == 0:
#         d.pop(nums[pre])
#     pre += 1
#
# print(ans)
